GermanWikipedia - /page/entry.mu

Micron Document

<!DOCTYPE html>

</head>

</header>

</div>

<p>Ein <b>Out-Tree</b> oder auch <b>Arboreszenz</b> ist in der <a href="Graphentheorie" title="Graphentheorie">Graphentheorie</a> ein spezieller <a href="Graph_(Graphentheorie)" title="Graph (Graphentheorie)">Graph</a>, genauer ein <a href="Gewurzelter_Baum" title="Gewurzelter Baum">gewurzelter Baum</a>, bei dem die Kanten von der Wurzel ausgehen. Der Gegensatz dazu ist der sogenannte <a href="In-Tree" title="In-Tree">In-Tree</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2></div>

<p>Eine Arboreszenz ist ein <a href="Gerichteter_Graph" title="Gerichteter Graph">gerichteter</a> Graph mit einem ausgezeichneten Knoten, der so genannten <a href="Wurzel_(Graphentheorie)" title="Wurzel (Graphentheorie)">Wurzel</a>, sodass jeder Knoten durch genau einen <a href="Gerichteter_Pfad" class="mw-redirect" title="Gerichteter Pfad">gerichteten Pfad</a> von der Wurzel aus erreichbar ist.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Weitere_Begriffe">Weitere Begriffe</h2></div>

<p>Der maximale <a href="Ausgangsgrad" class="mw-redirect" title="Ausgangsgrad">Ausgangsgrad</a> wird als <i>Ordnung</i> eines Out-Trees bezeichnet und alle Knoten mit Ausgangsgrad 0 bezeichnet man als <a href="Blatt_(Graphentheorie)" class="mw-redirect" title="Blatt (Graphentheorie)">Blätter</a>. Als <a href="Tiefe_(Graphentheorie)" class="mw-redirect" title="Tiefe (Graphentheorie)">Tiefe</a> eines Knotens bezeichnet man die Länge des Pfades von der Wurzel zu ihm und als <a href="H%C3%B6he_(Graphentheorie)" title="Höhe (Graphentheorie)">Höhe</a> des Out-Trees die Länge eines längsten Pfades.

</p><p>Wie bei <a href="Ungerichteter_Baum" title="Ungerichteter Baum">ungerichteten Bäumen</a> bezeichnet man auch in gewurzelten Bäumen alle Knoten, die kein Blatt sind, als <a href="Innerer_Knoten" class="mw-redirect" title="Innerer Knoten">innere Knoten</a>. Manchmal schließt man die Wurzel dabei aber aus.

</p><p>Bei einem <a href="(a%2Cb)-Baum" class="mw-redirect" title="(a,b)-Baum">(a,b)-Baum</a> haben alle Teilbäume die gleiche Tiefe.

</p><p><span id="Vorfahr"></span>Für einen von der Wurzel verschiedenen Knoten <i>v</i> bezeichnet man den Knoten, durch den er mit einer eingehenden Kante verbunden ist als <i>Vater</i>, <i>Vaterknoten</i>, <a href="Gewurzelter_Baum#Weitere_Begriffe" title="Gewurzelter Baum">Elternknoten</a> oder <i>Vorgänger</i> von <i>v</i>. Als <i>Vorfahren</i> von <i>v</i> bezeichnet man alle Knoten, die entweder Vater von <i>v</i> oder Vorgänger des Vaters sind.

</p><p>Umgekehrt bezeichnet man alle Knoten, die von einem beliebigen Knoten <i>v</i> aus durch eine ausgehende Kante verbunden sind als <i>Kinder</i>, <a href="Gewurzelter_Baum#Weitere_Begriffe" title="Gewurzelter Baum">Kindknoten</a>, <i>Sohn</i> oder <i>Nachfolger</i> von <i>v</i>. Als <i>Nachfahren</i> von <i>v</i> bezeichnet man Kinder von <i>v</i> oder deren Nachfahren. Als <i>Geschwister</i> oder <i>Geschwisterknoten</i> werden in einer Arboreszenz Knoten bezeichnet, die denselben <i>Vater</i> besitzen.

</p>

<div class="mw-heading mw-heading2"><h2 id="Alternative_Definition">Alternative Definition</h2></div>

<p>Out-Trees lassen sich auch <a href="Rekursion" title="Rekursion">rekursiv</a> definieren. Sie bestehen aus einem <a href="Knoten_(Graphentheorie)" title="Knoten (Graphentheorie)">Knoten</a> <i>w</i>, der die Wurzel des Baumes darstellt, welcher ausschließlich mit den Wurzeln knotendisjunkter Out-Trees <i>T</i><sub>1</sub>, <i>T</i><sub>2</sub>, ..., <i>T</i><sub><i>n</i></sub> verbunden ist, und zwar in Richtung der Wurzeln von <i>T</i><sub>1</sub>, <i>T</i><sub>2</sub>, ..., <i>T</i><sub><i>n</i></sub>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Siehe_auch">Siehe auch</h2></div>

<ul><li>Der <a href="Lowest_Common_Ancestor" title="Lowest Common Ancestor">letzte gemeinsame Vorfahr</a> als Ermittlungskonzept in der Graphentheorie</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li>Bernhard Korte, Jens Vygen: <cite style="font-style:italic">Aufspannende Bäume und Arboreszenzen</cite>. In: <cite style="font-style:italic">Kombinatorische Optimierung: Theorie und Algorithmen</cite>. Springer, Berlin, Heidelberg 2018, ISBN 978-3-662-57691-5, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>141–166</span>, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<span class="uri-handle" style="white-space:nowrap"><a rel="nofollow" class="external text" href="https://doi.org/10.1007/978-3-662-57691-5_6">10.1007/978-3-662-57691-5_6</a></span> (<a rel="nofollow" class="external text" href="https://link.springer.com/chapter/10.1007/978-3-662-57691-5_6">springer.com</a>).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Out-Tree&rft.atitle=Aufspannende+B%C3%A4ume+und+Arboreszenzen&rft.au=Bernhard+Korte%2C+Jens+Vygen&rft.btitle=Kombinatorische+Optimierung%3A+Theorie+und+Algorithmen&rft.date=2018&rft.doi=10.1007%2F978-3-662-57691-5_6&rft.genre=book&rft.isbn=9783662576915&rft.pages=141-166&rft.place=Berlin%2C+Heidelberg&rft.pub=Springer" style="display:none"> </span></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-1"><span class="mw-cite-backlink"><a href="#cite_ref-1">↑</a></span> <span class="reference-text">Willibald Dörfler, Jörg Mühlbacher: <cite style="font-style:italic">Graphentheorie für Informatiker</cite>. Walter de Gruyter, 2011, ISBN 978-3-11-083572-4, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>49<span style="display:inline-block;width:.2em"> </span>f</span>. (<a rel="nofollow" class="external text" href="https://www.google.de/books/edition/Graphentheorie_f%C3%BCr_Informatiker/5gOHuT6orEQC?hl=de&gbpv=1&pg=PA49&printsec=frontcover">google.de</a> [abgerufen am 31. Dezember 2024]).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Out-Tree&rft.au=Willibald+D%C3%B6rfler%2C+J%C3%B6rg+M%C3%BChlbacher&rft.btitle=Graphentheorie+f%C3%BCr+Informatiker&rft.date=2011-04-20&rft.genre=book&rft.isbn=9783110835724&rft.pages=49+f.&rft.pub=Walter+de+Gruyter" style="display:none"> </span></span>

</li>

</ol></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-05-25" href="https://de.wikipedia.org/wiki/?title=Out-Tree&oldid=256324812">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>